//: [Previous](@previous)

/*:
 # 桶排序
 * 最好情况 O(n+k))
 * 最坏情况 O(n^2))
 * 平均时间复杂度 O(n+k))
 * 空间复杂度 O(n+k)
 
 1. 设置固定数量的空桶。
 2. 把数据放到对应的桶中。
 3. 对每个不为空的桶中数据进行排序。
 4. 拼接不为空的桶中数据，得到结果
 
 */

import Foundation

var numbers = [3, 6, 5, 2, 7, 10, 1, 4, 3]
print("排序前 \(numbers)")

func buckerSort(_ arr: [Int]) -> [Int] {

    if arr.count < 2 {
        return arr
    }

    var min = arr[0], max = arr[0]
    for i in 1..<arr.count {
        if max < arr[i] {
            max = arr[i]
        }
        if min > arr[i] {
            min = arr[i]
        }
    }

    let size = 3
    let buckerNumber = (max-min+size)/size
    var buckers: [[Int]] = Array(repeating: [], count: buckerNumber)

    for item in arr {
        let index = (item - min) / buckerNumber
        buckers[index].append(item)
    }

    var nums: [Int] = []
    for bucker in buckers {
        nums += bubbleSort(bucker)
    }

    return nums
}

func bubbleSort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    }

    var nums = arr

    for i in 0..<nums.count {
        for j in 0..<nums.count-1-i {
            if nums[j] > nums[j+1] {
                nums.swapAt(j, j+1)
            }
        }
    }

    return nums
}

print("桶排序后 \(buckerSort(numbers))")

//: [Next](@next)
